NetNews Offline 2/NetNews Offline Volume 2.iso/news/comp/std/c/615

Text File | 1996-08-06 | 3.7 KB | 96 lines

Path: tbj.dec.com!diamond
From: [e-mail] (Norman Diamond)
Newsgroups: comp.std.c
Subject: Re: Restrictions on qsort compare function?
Date: 21 Mar 1996 03:44:27 GMT
Organization: Digital Equipment Corporation Japan , Tokyo
Message-ID: <4iqjar$[e-mail]>
References: <4iokop$[e-mail]>
Reply-To: [e-mail] (Norman Diamond)
NNTP-Posting-Host: jit533.tbj.dec.com

In article <4iokop$[e-mail]>, [e-mail] (James Bonfield) writes:
>Are there any limitations on what the sort function passed over to qsort can
>do or return?

Another followup stated a condition which is probably correct (the standard
isn't exactly explicit about it) but you are obeying that condition so it
is not your problem.

>I know it's meant to return < 0, 0 or > 0 for the various compare operations,
>but which you return is purely up to your own comparison system.

Exactly.

>On tracking down a bug in some old code I noticed that we had the
>compare function returning something like "a > b" instead of "b - a".
>Now this is obviously some silly bug in our coding,

Actually it's a silly question.  Just one sentence earlier, you gave the
exact reason why it doesn't matter if you do "a > b" instead of "a - b".
(Actually it can matter:  if "a - b" would overflow then doing "a > b"
will fix it instead of yielding undefined behavior :-)
On the other hand, doing "a > b" instead of "a < b" reverses the order
of the result -- no difference in technical validity, but likely only
one of these matches your requirement.

>such functions appear to make [one implementation's] qsort() function
>underflow the passed array.

This should not happen.

>#include <stdio.h>
>#include <stdlib.h>
>static int sort_func(const void *pa, const void *pb) {
>    const int *a = (int *)pa;
>    const int *b = (int *)pb;
>    return *a > *b;
>}

Incidentally, if you returned "a > b" instead of "*a > *b" then you would
likely be returning inconsistent results, violating the probably correct
condition which someone else posted.

>#define NUM_ELE 10
>int main() {
>    int i;
>    int crashme;     /* removing this line fixes things! */

This makes me suspicious that your test program is not exactly what you
posted, and your test program has a bug in some other part of its code
that already yielded undefined behavior.

>    int sortme[NUM_ELE];
>    srand(time(NULL));

Or it might be this bug right here.  The standard library function time()
returns type time_t which might not be int.  Your main() function assumes
that it must be int.  You can fix this by adding "#include <time.h>".

>    for (i=0; i<NUM_ELE; i++) {
>        sortme[i] = rand()%100+50;
>    }
>    qsort((void *)sortme, NUM_ELE, sizeof(int), sort_func);
>    return 0;
>}
>Adding some debugging information to this and printing up the array
>before and after sorting (including the values (666) immediately above
>and below the array) shows that the contents of memory outside of the
>array actually get swapped with memory inside the array. I can make it
>overflow too.

You probably have a bug in the other code that you haven't shown.
There's no 666 in the code you've shown.

>My understanding of this is that qsort() ought to be able to handle any
>sort function, even if it's something as dumb as (rand()%3)-1.

That would not be a sort function (it might even assert that a < b and
b < c and c < a).  As for whether qsort() is required to contend with
such nonsense, it "probably" isn't.
--
 <<  If this were the company's opinion, I would not be allowed to post it.  >>
"I paid money for this car, I pay taxes for vehicle registration and a driver's
license, so I can drive in any lane I want, and no innocent victim gets to call
the cops just 'cause the lane's not goin' the same direction as me" - J Spammer